As computer networks become increasingly more complex, more and more end stations communicate through more and more intermediate links. An intermediate link is typically a section of network cable with nodes or network switches at each end of the cable. A link can carry only a predetermined amount of network traffic, usually expressed as a bit per second limit. Network traffic is typically referred to as packets or cells, and each packet or cell requires a number of bits to be transmitted over the network.
For example, an intermediate link may carry traffic originating at numerous source end stations. And each source end station may be capable of generating network traffic at a rate in excess of what the intermediate link can handle without dropping packets. That is, each individual end station may be capable of driving an intermediate link into congestion. Accordingly, when a plurality of end stations are creating network traffic, and all of that traffic passes through a particular intermediate link, it is clear that a mechanism must be installed to limit the traffic created by the source end stations. Flow control is the generic term used to describe a mechanism to limit traffic created by source end stations.
A bottleneck resource is a link, or a switch, etc. which limits the flow through the network.
Recently, end to end rate based flow control schemes have been gaining popularity, especially in ATM networks (for background information see User-Network Interface Specification Version 4.0, The ATM Forum, known as the UNI 4.0 Specification, all disclosures of which are incorporated herein by reference). The goal of a rate based flow control scheme is to determine a rate at which a flow can transmit data so that the bottleneck resource is shared in a fair and efficient manner.
There has been considerable work on congestion management in high speed networks in the recent past, using rate based congestion/flow control schemes, which operate either in an end-to-end framework or on a hop-by-hop basis. The use of rate based flow control schemes, with all of the sources cooperating in order to maintain a smooth rate of flow of data from each of them, has the promise of significantly reducing the buffer requirements in the switches. Much of this work has been in the context of ATM, especially for the ABR (Available Bit Rate) service. The ABR service is typically used for data transfer, and is considered to be lower priority than the other classes of service such as CBR (Constant Bit Rate) and VBR (Variable Bit Rate). Left over bandwidth from the use of a resource (link, switch or end-system) by CBR and VBR is used for ABR service. Therefore, the timely use of the available resources by ABR without causing congestion (that may result either in significantly increase dequeueing delay or cell loss) is an important goal. Another equally important goal is to ensure that the resources in the network are shared in a `fair and equitable` manner.
End-to-end rate schemes, as well as the dynamic buffer allocation in a hop-by-hop credit based scheme, use the transmission rate as the meaningful characteristic of a flow. This has also been the basis of past work in packet networks with high bandwidth-delay products, with the focus on determining the rate at which a flow must transmit data so that a bottleneck's capacity is shared fairly and efficiently among the flows utilizing the bottleneck.
A definition of "fairness" is the notion of Max-Min fairness, which has been adopted in the ATM Forum for congestion management of the ABR service.
In general, explicit rate schemes work as follows: Resource Management (RM) cells (or probes) are sent from, and received by, the sources to determine the explicit rate at which the sources may transmit. Switches determine a rate allocation value based on local information and on the information provided to them in RM cells, and return this rate allocation value back to the source explicitly in the RM cells.
A goal of computation at the switch is to compute Max-Min rate allocation value based on the information which the switch receives from traffic through the switch, particularly information received from an RM cell.
There are several ways of computing the Max-Min fair rate allocation value for a flow in a network of multiple resources and multiple flows with different resource demands.
A straightforward computation of Max-Min fair rate allocation value requires state information for each virtual circuit, that is "per VC state". And so the calculation must scan all VCs per "RM cell time", and this may be a prohibitive amount of calculational work. There have been many attempts to overcome this complexity in calculation, but such attempts typically come at the price of degrading the convergence properties necessary for stable operation of the network.
There is needed a computational method for allocating transmission rate to source end nodes, and which both reduces the computational complexity, and reduces the state information which must be retained concerning each VC, without significantly degrading convergence properties for the network. Also, the computational method should be useful with either interval based or proportional schemes of flow control.